{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 第七章 链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "list类的缺点：\n",
    "\n",
    "1. 一个动态数组的长度可能超过实际存储数组元素所需的元素。\n",
    "2. 在实时系统中对操作的摊销边界是不可接受的。\n",
    "3. 在一个数组内部执行插入和删除操作的代价太高。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "数组集中存储数据，链表则是分布存储，采用轻量级对象——节点，每个节点维护一个指向它的元素的引用，并含一个或者多个指向相邻节点的引用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.1 单向链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "单向链表：每个节点含有两个成员，元素成员引用任意一个对象，该对象是序列中的一个元素；指针域成员指向单向链表的后继节点。（若没有下一个元素则为空）\n",
    "\n",
    "链表的第一个和最后一个节点分别称为头结点和为节点，可以用next方法从一个节点移动到下一个节点。这个过程称为遍历链表、链接跳跃或者指针跳跃。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "链表的第一个和最后一个节点分别称为头结点和为节点，可以用`next`方法从一个节点移动到下一个节点。这个过程称为遍历链表、链接跳跃或者指针跳跃。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "链表的每个节点也可以不指向元素的引用而是直接存储元素，同时指向下一个节点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "每个节点是一个实例，所有节点组成的链表也是一个实例。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "链表必须有指向头节点的引用，相当于第一个元素的存储位置，其他节点包括尾节点的引用可以通过遍历链表实现。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了防止尾节点的访问效率过低，可以存储一个指向尾节点的引用。同样道理，也将链表的长度或者大小存储起来，获得长度就只需要O(1)，这是以空间换时间。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "节点是一个个实例，next是实例变量，可以存储为下一个节点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 在单向链表的头部插入一个元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "单向链表没有预定的大小，占用空间取决于当前元素的个数，这是由链表分布存储决定，没有数组集中存储所存在的障碍。（如动态数组可能会扩大或者收缩，也可能因为内存不足够而迁移数组）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在头部插入元素需要的步骤：\n",
    "\n",
    "1. 创建一个新的节点。\n",
    "2. 节点指向之前的头部节点。\n",
    "3. 头节点指向新节点。（记录新的头部节点，对于链表而言，头节点的位置很重要）\n",
    "4. 链表的长度加1。（链表的长度是由一个变量进行维护的）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 在单向链表的尾部插入一个元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果没有保存尾节点的引用，则很麻烦，如果保存了，那步骤如下：\n",
    "\n",
    "1. 创建一个新的节点。\n",
    "2. 新节点指向None。\n",
    "3. 原来的尾节点指向新节点。\n",
    "4. 尾节点引用变量指向新节点。\n",
    "5. 链表的长度加1。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 从单向链表中删除一个元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从头部删除一个元素：\n",
    "\n",
    "1. 判断链表是否为空。\n",
    "2. 头节点引用变量指向下一个节点。\n",
    "3. 链表长度减1。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "删除尾部的元素则较难，因为要将尾部指针指向尾节点的前一个节点，但是即便尾部指针指向了尾节点，也无法像头部指针指向头节点再调用`next`方法一样来指向第二个节点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 手写链表个人尝试"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里手写的链表只支持头部添加和删除节点。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "class Empty(Exception):\n",
    "    pass\n",
    "\n",
    "class LinkedList:\n",
    "    \n",
    "    class _Node:\n",
    "        \n",
    "        __slots__ = '_element', '_next'\n",
    "        \n",
    "        def __init__(self, element, next):\n",
    "            self._element = element\n",
    "            self._next = next\n",
    "\n",
    "    def __init__(self):\n",
    "        self._size = 0                 ## 维护一个长度\n",
    "        self._head = None              ## 维护一个头指针\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "        \n",
    "    def add_head(self, e):\n",
    "        self._head = self._Node(e, self._head)\n",
    "        self._size += 1\n",
    "    \n",
    "    def delete_head(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Linked-list is empty!')\n",
    "        self._head = self._head._next\n",
    "        self._size -= 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 7.1.1 用单向链表实现栈 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "由于栈需要压入和弹出操作，因此用单向链表实现栈时，需要考虑如何用链表高效实现压入和弹出操作。如果是压入，相当于往链表中增加元素，因此可以选择单向链表的头部或者尾部作为栈顶，但是还需要弹出即删除操作，因此最好选择单向链表的头部作为栈顶。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "栈的节点，需要定义一个类，作为栈类的嵌套类，且非公有。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "单向链表实现栈的代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Empty(Exception):\n",
    "    pass\n",
    "\n",
    "class LinkedStack:\n",
    "    \n",
    "    class _Node:\n",
    "        \n",
    "        __slots__ = '_element', '_next'\n",
    "        \n",
    "        def __init__(self, element, next):\n",
    "            self._element = element\n",
    "            self._next = next\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._head = None                         ## 头指针，初始化一个空栈，头指针指向None\n",
    "        self._size = 0                            ## 栈的长度，初始化一个空栈，长度为0\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "    \n",
    "    def push(self, e):\n",
    "        self._head = self._Node(e, self._head)\n",
    "        self._size += 1\n",
    "    \n",
    "    def top(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Stack is empty!')\n",
    "        return self._head._element\n",
    "    \n",
    "    def pop(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Stack is empty!')\n",
    "        answer = self._head._element\n",
    "        self._head = self._head._next\n",
    "        self._size -= 1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`S.push、S.pop、S.top、len(S)、S.is_empty`等的运行时间都是O(1)，且不需要摊销。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 7.1.2 用单向链表实现队列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "队列的两端都需要进行操作，所以需要维护两个变量`_head`、`_tail`，且由于队首需要删除元素，所以将队首作为链表的头部。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Empty(Exception):\n",
    "    pass\n",
    "\n",
    "class LinkedQueue:\n",
    "    \n",
    "    class _Node:\n",
    "        \n",
    "        __slots__ = '_element', '_next'\n",
    "        \n",
    "        def __init__(self, element, next):\n",
    "            self._element = element\n",
    "            self._next = next\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._head = None\n",
    "        self._tail = None\n",
    "        self._size = 0\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "    \n",
    "    def first(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Queue is empty!')\n",
    "        return self._head._element\n",
    "    \n",
    "    def dequeue(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Queue is empty!')\n",
    "        answer = self._head._element\n",
    "        self._head = self._head._next\n",
    "        self._size -= 1\n",
    "        if self.is_empty():\n",
    "            self._tail = None\n",
    "        return answer\n",
    "    \n",
    "    def enqueue(self, e):                              \n",
    "        newest = self._Node(e, None)\n",
    "        if self.is_empty():\n",
    "            self._head = newest\n",
    "        else:\n",
    "            self._tail._next = newest                         \n",
    "        self._tail = newest                                   ## 这里维护了尾指针\n",
    "        self._size += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "所有操作的运行时间均为O(1)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.2 循环链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "循环链表：尾节点的next指向头节点形成一个循环的结构，同时使得链表的开始和结尾没有固定的位置，不过必须像单向链表一样维护一个`_head`之类的指针——`current`，否则无法使用该循环链表。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 7.2.1 轮转调度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "循环调度：循环遍历每一个元素，提供“服务”。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "队列提供循环调度服务的过程就是一个元素离队（队首），接受服务，再入队（正常队列则不再入队）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "循环链表实现循环队列代码如下：（循环链表是尾节点指向头节点，循环队列是出队后入队）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Empty(Exception):\n",
    "    pass\n",
    "\n",
    "class CircularQueue:\n",
    "    \n",
    "    class _Node:\n",
    "        \n",
    "        __slots__ = '_element', '_next'\n",
    "        \n",
    "        def __init__(self, element, next):\n",
    "            self._element = element\n",
    "            self._next = next\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._tail = None\n",
    "        self._size = 0\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "    \n",
    "    def first(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Queue is empty!')\n",
    "        return self._tail._next._element\n",
    "    \n",
    "    def dequeue(self):                             ## 这里出队没有直接再入队，再入队的定义为rotate方法\n",
    "        if self.is_empty():\n",
    "            raise Empty('Queue is empty!')\n",
    "        oldhead = self._tail._next\n",
    "        if self._size == 1:\n",
    "            self._tail = None\n",
    "        else:\n",
    "            self._tail._next = oldhead._next\n",
    "        self._size -= 1\n",
    "        return oldhead._element\n",
    "    \n",
    "    def enqueue(self, e):\n",
    "        newest = self._Node(e, None)\n",
    "        if self.is_empty():\n",
    "            newest._next = newest                   ## 这里体现循环链表，如果不是循环链表，那么维护头尾指针都为newest\n",
    "        else:\n",
    "            newest._next, self._tail._next = self._tail._next, newest\n",
    "        self._tail = newest                         ## 尾指针一定是指向最新入队的\n",
    "        self._size += 1\n",
    "    \n",
    "    def rotate(self):                               ## 循环链表体现在尾节点指向头节点，循环队列体现在这个方法\n",
    "        if self._size > 0:\n",
    "            self._tail = self._tail._next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.3 双向链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "单向链表的节点维护了一个后继节点的引用，这种单向的引用导致了一些问题，如删除某个指针指向的节点，由于无法通过该节点找到前一个节点（需要修改前一个节点的next），所以会使删除操作变得困难。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "双向链表：各个节点维护前一个节点和后一个节点两个引用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "头哨兵、尾哨兵：头部和尾部多添加两个节点，但不存储元素，用于避免因操作接近边界而导致的特殊情况。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于有哨兵的空链表：头哨兵的next指向尾哨兵，尾哨兵的prev指向头哨兵。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "头哨兵和尾哨兵的好处：插入和删除操作总是在节点之间进行（即便其中一个或者两个节点可能是哨兵），可以统一定义。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "之前在插入元素的时候得考虑向空链表插入元素的特殊情况，现在则不用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "双向链表的插入操作：更改前一个节点的next为新节点，新节点的next为后一个节点，新节点的prev为前一个节点，后一个节点的prev为新节点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "双向链表的删除操作：更改前一个节点的next和后一个节点的prev使他们彼此连接即可。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 7.3.1 双向链表的基本实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "链表可以支持在最坏情况下O(1)运行时间的插入和删除操作，不过需要提前有一个插入和删除位置的引用或者指针。如果位置由索引给出，则需要遍历，是很不方便的，对于数组，索引可以用于计算内存地址，链表则不行。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "之前实现栈和队列对链表的挑战并不大，因为弹出、压入、入队、离队都是在两端进行的。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Empty(Exception):\n",
    "    pass\n",
    "\n",
    "class _DoublyLinkedBase:\n",
    "    \n",
    "    class _Node:\n",
    "        \n",
    "        def __init__(self, element, prev, next):\n",
    "            self._element = element\n",
    "            self._prev = prev\n",
    "            self._next = next\n",
    "        \n",
    "    def __init__(self):\n",
    "        self._header = self._Node(None, None, None)\n",
    "        self._tailer = self._Node(None, None, None)\n",
    "        self._header._next = self._tailer\n",
    "        self._tailer._prev = self._header\n",
    "        self._size = 0\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "    \n",
    "    def _insert_between(self, e, predecessor, successor):\n",
    "        newest = self._Node(e, predecessor, successor)\n",
    "        predecessor._next = newest\n",
    "        successor._prev = newest\n",
    "        self._size += 1\n",
    "        return newest\n",
    "    \n",
    "    def _delete_node(self, node):\n",
    "        predecessor = node._prev\n",
    "        successor = node._next\n",
    "        predecessor._next = successor                           ## 节点是可变类\n",
    "        successor._prev = predecessor\n",
    "        self._size -= 1\n",
    "        element = node._element\n",
    "        node._prev = node._next = node._element = None          ## 将删除的节点中的数据都清空\n",
    "        return element"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "节点`_Node`是可变类，提供节点的引用可以进行插入或者删除操作，通过引用是可以对节点实例的变量进行修改的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 7.3.2 用双向链表实现双端队列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "双端队列需要实现队首和队尾的入队和离队操作，虽然双向链表中定义了任意位置插入和删除的操作，但是双向链表的插入和删除操作包括双向链表本身都是私有的，我们写的公共接口不支持`插队`行为。而我们的入队和离队行为则依靠双向链表的非公有的插入和删除元素的方法进行。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "虽然双向链表的插入和删除操作都需要前后节点的引用，这导致在任意位置插入和删除节点是不容易的，但是由于双向链表存储了头指针和尾指针，指向头哨兵和尾哨兵，可以通过next和prev方法引用入队和离队所需的节点，这是十分巧妙的一种设计。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedDeque(_DoublyLinkedBase):        ## 继承省去了初始化和一些相同的方法，如果是适配器，则两个类在更大程度上存在不同\n",
    "    \n",
    "    def first(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Deque is empty!')\n",
    "        return self._header._next._element\n",
    "    \n",
    "    def last(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Deque is empty!')\n",
    "        return self._tailer._prev._element\n",
    "    \n",
    "    def insert_first(self, e):\n",
    "        self._insert_between(e, self._header, self._header._next)\n",
    "        \n",
    "    def insert_last(self, e):\n",
    "        self._insert_between(e, self._tailer._prev, self._tailer)\n",
    "    \n",
    "    def delete_first(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Deque is empty!')\n",
    "        self._delete_node(self._header._next)\n",
    "    \n",
    "    def delete_last(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Deque is empty!')\n",
    "        return self._delete_node(self._tailer._prev)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.4 位置列表的抽象数据类型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "队列存在限制，排队到一半的人不能离队，而现实生活中可能也存在一些插队情况。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "找到链表中一个给定索引的元素，需要从链表的开始或者结束的位置起逐个遍历从而计算出目标元素的位置。（链表会维护头指针和尾指针，以高效找到头节点和尾节点）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "索引的一个缺点是，当序列发生变化时，索引对应的元素可能与之前不同，元素对应的索引可能发生了变化。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于链表而言，节点的引用代替索引成为标注位置的方式。给出节点引用的基础上，执行插入和删除操作都只需要常量时间。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 7.4.1 含位置信息的列表抽象数据类型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "位置实例支持的方法：p.element()，可以访问存储在位置p的元素。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "位置列表支持的方法：\n",
    "\n",
    "1. L.first() -- 返回L中的第一个元素的位置，L为空返回None。\n",
    "2. L.last() -- 同上。\n",
    "3. L.before(p) -- 返回L中紧邻的前面元素的位置，如果p为第一个元素，则返回None。\n",
    "3. L.after(p) -- 同上。\n",
    "4. L.is_empty() -- 是否为空。\n",
    "5. len(L) -- 返回列表元素的个数。\n",
    "6. iter(L) -- 返回迭代器。\n",
    "\n",
    "支持的更新方法：\n",
    "\n",
    "1. L.add_first(e) -- 在L的前面插入新元素e，返回新元素的位置。\n",
    "2. L.add_last(e) -- 同理。\n",
    "3. L.add_before(p, e) -- 在L中位置p之前插入一个新元素e，返回新元素的位置。\n",
    "4. L.add_after(p, e) -- 同理。\n",
    "5. L.replace(p, e) -- 用元素e取代位置p处的元素，返回之前p位置处的元素。\n",
    "6. L.delete(p) -- 删除并且返回L中位置p处的元素，取消该位置。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 7.4.2 双向链表实现位置列表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "位置列表很关键的一点在于，用户输入和返回的一定是位置而不是节点，因为节点是非公开的而位置是封装起来的节点。还有一点也很重要，位置列表区别于数组，数组用索引表示元素的位置，但是索引会因为数组的更新而改变，而位置列表使用位置，或者说间接使用节点来表示元素的位置，数组的更新对位置与元素的对应关系并无影响，有了位置，获得元素或者插入元素永远只需要线性时间，这本质上是链表与数组之间的区别。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "命题：双向链表实现位置列表的所有操作的最坏运行时间为常数时间。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`PosionalList`将继承`_DoublyLinkedList`类，嵌套类`Position`可能引用相同的节点，因此定义`__eq__`和`__ne__`方法以判断是否引用相同节点，定义`_validate`方法以判断输入的节点是否属于当前`PositionalList`，在定义`_validate`方法时识别弃用节点的标准时，节点的前后引用都是None。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "访问和更新的方法的实现：依赖于方法`_make_position`和方法`_insert_between`。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "位置列表的代码实现如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "class PositionalList(_DoublyLinkedBase):\n",
    "    \n",
    "    class Position:\n",
    "        \n",
    "        def __init__(self, container, node):\n",
    "            self._container = container\n",
    "            self._node = node\n",
    "        \n",
    "        def element(self):\n",
    "            return self._node._element\n",
    "        \n",
    "        def __eq__(self, other):\n",
    "            return type(other) is type(self) and other._node == self._node\n",
    "        \n",
    "        def __ne__(self, other):\n",
    "            return not(self == other)\n",
    "        \n",
    "    def _validate(self, p):\n",
    "        if not isinstance(p, self.Position):\n",
    "            raise TypeError('p must be proper Position type')\n",
    "        if p._container is not self:\n",
    "            raise ValueError('p does not belong to this container')\n",
    "        if p._node._next is None and p._node._prev is None:            ## 书上只看next，感觉不太对\n",
    "            raise ValueError('p is no longer valid')\n",
    "        return p._node\n",
    "    \n",
    "    def _make_position(self, node):\n",
    "        if node is self._header or node is self._tailer:               ## 这里目的是让链接到头尾哨兵时返回None以构成before和after方法\n",
    "            return None\n",
    "        else:\n",
    "            return self.Position(self, node)\n",
    "    \n",
    "    def first(self):\n",
    "        return self._make_position(self, self._header._next)\n",
    "    \n",
    "    def last(self):\n",
    "        return self._make_position(self, self._tailer._prev)\n",
    "    \n",
    "    def before(self, p):\n",
    "        node = self._validate(p)\n",
    "        return self._make_position(self, node._prev)\n",
    "    \n",
    "    def after(self, p):\n",
    "        node = self._validate(p)\n",
    "        return self._make_position(self, node._next)\n",
    "    \n",
    "    def __iter__(self):\n",
    "        cursor = self.first()\n",
    "        while cursor is not None:\n",
    "            yield cursor.element()\n",
    "            cursor = self.after(cursor)\n",
    "    \n",
    "    def _insert_between(self, e, predecessor, successor):\n",
    "        node = super()._insert_between(e, predecessor, successor)\n",
    "        return self._make_position(node)\n",
    "    \n",
    "    def add_first(self, e):\n",
    "        return self._insert_between(e, self._tailer._prev, self._tailer)\n",
    "    \n",
    "    def add_before(self, p, e):\n",
    "        original = self,_validate(p)\n",
    "        return self._insert_between(e, original._prev, original)\n",
    "    \n",
    "    def add_aftre(self, p, e):\n",
    "        original = self._validate(p)\n",
    "        return self._insert_between(e, original, original._next)\n",
    "    \n",
    "    def delete(self, p):\n",
    "        original = self._validate(p)\n",
    "        return self._delete_node(original)\n",
    "    \n",
    "    def replace(self, p, e):\n",
    "        original = self._validate(p)\n",
    "        old_value = original._element\n",
    "        original._element = e\n",
    "        return old_value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.5 位置列表的排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "位置列表的排序使用插入排序，由于之前的基于数组的插入排序使用的是索引，所以不必维护位置的引用，这里由于没有索引，因此在比较之前，需要先找到当前元素的位置以及要比较的元素的位置，这可以通过维护一个引用来实现。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注：这里如果marker后一个比marker大，则不需变化，只需marker后移，如果marker后一个比marker小，则将被删除并插入到前面，marker不需要变化。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion_sort(L):\n",
    "    if len(L) > 1:\n",
    "        marker = L.first()\n",
    "        while marker != L.last():\n",
    "            pivot = L.after(marker)\n",
    "            value = pivot.element()\n",
    "            if value > marker.element():\n",
    "                marker = pivot\n",
    "            else:\n",
    "                walk = marker\n",
    "                while walk != L.first() and L.before(walk).element > value:\n",
    "                    walk = L.before(walk)\n",
    "                L.delete(pivot)\n",
    "                L.add_before(walk, value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.6 案例研究：维护访问频率"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "维护一个元素的集合，保存元素的访问数量，适用的场景：用户访问最多的URL、用户最喜欢的音乐，比如用这个新的数据结构来构建一个收藏夹。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "抽象数据类型：\n",
    "\n",
    "1. access(e): 访问元素e，增加其访问数量，如果它尚未存在于收藏夹中，会将它添加进去\n",
    "2. remove(e): 从收藏夹列表中移除元素e，前提是存在这样的e\n",
    "3. top(k): 返回前k个访问最多的元素的迭代器。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 7.6.1 使用有序表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "管理收藏夹的第一种方法是在链表中存储元素，按访问次数的降序顺序来存储这些元素。每次访问一个元素时，可能会改变该元素的位置，这里使用向后遍历的插入排序来寻找该元素的新位置。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里使用PositionalList类作为存储实现一个收藏夹列表，由于二者的差别较大，所以不使用继承，而是采用适配器模式。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一个通用的面向对象的设计模式——组合模式，定义一个存储两个或者两个以上的对象的对象，类似于元组、列表等，只不过是自定义的类，这里在FavoritesList类中定义了一个非公有的嵌套类，可以同时维护元素和元素的访问次数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "class FavoritesList:\n",
    "    \n",
    "    class _Item:                                              ## 该类的更新方法在FavoritesList中定义，而不在自己这个类中定义\n",
    "        \n",
    "        __slots__ = '_value', '_count'                        ## 作用是轻量级\n",
    "        \n",
    "        def __init__(self, e):\n",
    "            self._value = e\n",
    "            self._count = 0\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._data = PositionalList()\n",
    "        \n",
    "    def _find_position(self, e):\n",
    "        walk = self._data.first()\n",
    "        while walk is not None and walk.element()._value != e:\n",
    "            walk = self._data.after(walk)\n",
    "        return walk\n",
    "    \n",
    "    def _move_up(self, p):\n",
    "        if p != self._data.first():\n",
    "            cnt = p.element()._count\n",
    "            walk = self._data.before(p)\n",
    "            if cnt > walk.element()._count:\n",
    "                while (walk != self._data.first() and cnt > self._data.before(walk).element()._count):\n",
    "                    walk = self._data.before(walk)\n",
    "                self._data.add_before(walk, self._data.delete(p))\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self._data)\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return len(self._data) == 0\n",
    "    \n",
    "    def access(self, e):\n",
    "        p = self._find_position(e)\n",
    "        if p is None:\n",
    "            p = self._data.add_last(self._Item(e))\n",
    "        p.element()._count += 1\n",
    "        self._move_up(p)\n",
    "    \n",
    "    def remove(self, e):\n",
    "        p = self._find_position(e)\n",
    "        if p is not None:\n",
    "            self._data.delete(p)\n",
    "    \n",
    "    def top(self, k):\n",
    "        if not 1 <= k <= len(self):\n",
    "            raise ValueError('Illegal value for k')\n",
    "        walk = self._data.first()\n",
    "        for j in range(k):\n",
    "            item = walk.element()\n",
    "            yield item._value\n",
    "            walk = self._data.after(walk)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 7.6.2 启发式动态调整列表（Move-to-Font）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "每次访问一个元素时，将该元素挪至第一位，原理是人很可能在短时间内访问多次同一个元素。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "class FavoritesListMTF(FavoritesList):\n",
    "    \n",
    "    def _move_up(self, p):\n",
    "        if p != self._data.first():\n",
    "            self._data.add_first(self._data.delete(p))\n",
    "    \n",
    "    def top(self, k):\n",
    "        if not 1 <= k <= len(self):\n",
    "            raise ValueError('Illegal value for k')\n",
    "        temp = PositionalList()\n",
    "        for item in self._data:\n",
    "            temp.add_last(item)\n",
    "        for j in range(k):\n",
    "            highPos = temp.first()\n",
    "            walk = temp.after(highPos)\n",
    "            while walk is not None:\n",
    "                if walk.element()._count > highPos.element()._count:\n",
    "                    highPos = walk\n",
    "                walk = temp.after(walk)\n",
    "            yield highPos.element()._value\n",
    "            temp.delete(highPos)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.7 基于链表的序列和基于数组的序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基于数组序列的优点：\n",
    "\n",
    "1. 基于索引，访问元素O(1)时间复杂度。\n",
    "2. 通常情况下，数组的常量时间比链表的常量时间要短。（比如用数组和链表分别实现队列，并进行入队操作，数组的操作会更快，虽然都是O(1)）。\n",
    "3. 相较于链式结构，数组所需要的存储空间更少。因为链表引用的存储是很占空间的，不仅要存储元素，还要存储链接的节点。\n",
    "\n",
    "基于链表序列的优点：\n",
    "\n",
    "1. 链表不需要摊销，基于链表的结构可以为操作提供最坏情况的时间界限。\n",
    "2. 链表可以在任意位置进行时间复杂度为O(1)的插入和删除操作。（这在文本编辑器的存储结构中可能是很有用的）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.8 练习"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "R-7.7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Empty(Exception):\n",
    "    pass\n",
    "\n",
    "class LinkedQueue:\n",
    "    \n",
    "    class _Node:\n",
    "        \n",
    "        __slots__ = '_element', '_next'\n",
    "        \n",
    "        def __init__(self, element, next):\n",
    "            self._element = element\n",
    "            self._next = next\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._head = None\n",
    "        self._tail = None\n",
    "        self._size = 0\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "    \n",
    "    def first(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Queue is empty!')\n",
    "    \n",
    "    def dequeue(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Queue is empty!')\n",
    "        answer = self._head._element\n",
    "        self._head = self._head._next\n",
    "        self._size -= 1\n",
    "        if self.is_empty():\n",
    "            self._tail = None\n",
    "        return answer\n",
    "    \n",
    "    def enqueue(self, e):                              \n",
    "        newest = self._Node(e, None)\n",
    "        if self.is_empty():\n",
    "            self._head = newest\n",
    "        else:\n",
    "            self._tail._next = newest                         \n",
    "        self._tail = newest                                   ## 这里维护了尾指针\n",
    "        self._size += 1\n",
    "    \n",
    "    def rotate(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Queue is empty!')\n",
    "        self.enqueue(self.dequeue)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C-7.24"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "头哨兵的好处是空栈在实际上也不为空，始终有一个头哨兵，因此在`pop`和`top`时不需考虑`Empty`错误。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class HeadLinkedStack:\n",
    "    \n",
    "    class _Node:\n",
    "        \n",
    "        __slots__ = '_element', '_next'\n",
    "        \n",
    "        def __init__(self, element, next):\n",
    "            self._element = element\n",
    "            self._next = next\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._head = self._Node(None, None)                ## 头哨兵                      \n",
    "        self._size = 0                          \n",
    "    \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "    \n",
    "    def push(self, e):\n",
    "        self._head._next = self._Node(e, self._head)\n",
    "        self._size += 1\n",
    "    \n",
    "    def top(self):\n",
    "        return self._head._next\n",
    "    \n",
    "    def pop(self):\n",
    "        answer = self._head._next._element\n",
    "        self._head._next = self._head._next._next\n",
    "        self._size -= 1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C-7.25"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class HeadLinkedQueue:\n",
    "    \n",
    "    class _Node:\n",
    "        \n",
    "        __slots__ = '_element', '_next'\n",
    "        \n",
    "        def __init__(self, element, next):\n",
    "            self._element = element\n",
    "            self._next = next\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._head = self._Node(None, None)\n",
    "        self._tail = None                                    ## 需要维护一个队尾的引用\n",
    "        self._size = 0\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "    \n",
    "    def first(self):\n",
    "        return self._head._next._element\n",
    "    \n",
    "    def dequeue(self):\n",
    "        answer = self._head._next._element\n",
    "        self._head._next = self._head._next._next\n",
    "        self._size -= 1\n",
    "        return answer\n",
    "    \n",
    "    def enqueue(self, e):\n",
    "        newest = self._Node(e, None)\n",
    "        if self.is_empty():\n",
    "            self._head._next = newest\n",
    "        else:\n",
    "            self._tail._next = newest\n",
    "        self._tail = newest                                   ## 维护尾指针\n",
    "        self._size += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C-7.26"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Empty(Exception):\n",
    "    pass\n",
    "\n",
    "class LinkedQueue:\n",
    "    \n",
    "    class _Node:\n",
    "        \n",
    "        __slots__ = '_element', '_next'\n",
    "        \n",
    "        def __init__(self, element, next):\n",
    "            self._element = element\n",
    "            self._next = next\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._head = None\n",
    "        self._tail = None\n",
    "        self._size = 0\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "    \n",
    "    def first(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Queue is empty!')\n",
    "        return self._head._element\n",
    "    \n",
    "    def dequeue(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Queue is empty!')\n",
    "        answer = self._head._element\n",
    "        self._head = self._head._next\n",
    "        self._size -= 1\n",
    "        if self.is_empty():\n",
    "            self._tail = None\n",
    "        return answer\n",
    "    \n",
    "    def enqueue(self, e):                              \n",
    "        newest = self._Node(e, None)\n",
    "        if self.is_empty():\n",
    "            self._head = newest\n",
    "        else:\n",
    "            self._tail._next = newest                         \n",
    "        self._tail = newest                                   ## 这里维护了尾指针\n",
    "        self._size += 1\n",
    "    \n",
    "    def concatenate(self, Q):\n",
    "        self._tail._next = Q._head\n",
    "        Q._head = None                                        ## 初始化Q\n",
    "        Q._tail = None\n",
    "        Q._size = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C-7.28"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "单向链表反转几种方法：\n",
    "\n",
    "1. 递归。 -- 万物皆可递归\n",
    "2. 将链表所有节点存储到一个序列，然后反转。 -- 浪费太多内存\n",
    "3. 遍历，三个指针，每次将中间指针next指向第一个指针，然后改变三个指针位置。 -- 理论上两个也够\n",
    "4. 遍历，从第二个节点往后，依次将节点插入到第一个节点后面，最后将第一个节点插入到末尾。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "385.4px",
    "left": "770px",
    "top": "184.6px",
    "width": "339.4px"
   },
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
